import heapq
from typing import List


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])
        heap = [(0,(0,0))]
        minDistance = [[float('inf') for _ in range(n)] for _ in range(m)]
        minDistance[0][0] = 0
        while heap:
            cost,(x,y) = heapq.heappop(heap)
            if cost > minDistance[x][y]: continue
            for nx, ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if nx < 0 or nx >= m: continue
                if ny < 0 or ny >= n: continue
                new_dis = max(cost, abs(heights[x][y]-heights[nx][ny]))
                if new_dis >= minDistance[nx][ny]: continue
                minDistance[nx][ny] = new_dis
                heapq.heappush(heap, (new_dis, (nx,ny)))
        return minDistance[m-1][n-1]

if __name__ == '__main__':
    s = Solution()
    r = s.minimumEffortPath([[1,2,2],[3,8,2],[5,3,5]])
    print(r)